package com.leetcode.linkedlist;

/**
 * 排序链表
 * 给你链表的头结点head，请将其按 升序 排列并返回 排序后的链表 。
 * 进阶：
 * 你可以在O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * 示例 1：
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 示例 2：
 * 输入：head = [-1,5,3,4,0]
 * 输出：[-1,0,3,4,5]
 * 示例 3：
 * 输入：head = []
 * 输出：[]
 * 提示：
 * 链表中节点的数目在范围[0, 5 * 104]内
 * -105<= Node.val <= 105
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa262d/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年11月18日 16:54
 */
 class Code148 {
    public static void main(String[] args) {
        Code148 code03 = new Code148();
        ListNode l0 = new ListNode(4);
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(3);
        l0.next = l1;
        l1.next = l2;
        l2.next = l3;
        System.out.println(l0);
        ListNode node =  code03.sortList3(l0);
        System.out.println(node);
    }
    /**
     * 低效率插入排序
     * @author ymy
     * @date 2021/11/19 13:28
     * @param head
     * @return com.leetcode.linkedlist.Code03.ListNode
     */
    public ListNode sortList(ListNode head) {
       ListNode p = head;
        while (p != null){
            ListNode tar = findMin(p);
            if(tar != p){
                int temp = tar.val;
                tar.val = p.val;
                p.val = temp;
            }
            p = p.next;
        }
        return head;
    }
    public ListNode findMin(ListNode node) {
        ListNode p = node;
        ListNode minp = node;
        int min = node.val;
        while (p != null){
            if(p.val < min){
                min = p.val;
                minp = p;
            }
            p = p.next;
        }
        return minp;
    }
    /**
     * 插入排序
     * @author ymy
     * @date 2021/11/19 13:28
     * @param head
     * @return com.leetcode.linkedlist.Code03.ListNode
     */
    public ListNode sortList2(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode helpNode = new ListNode(0);
        helpNode.next = head;
        ListNode lastNode = head;
        ListNode tarNode = head.next;
        while(tarNode != null){
            if(lastNode.val <= tarNode.val){
                lastNode = lastNode.next;
            }else {
                ListNode pre = helpNode;
                while(pre.next.val <= tarNode.val){
                    pre = pre.next;
                }
                lastNode.next = tarNode.next;
                tarNode.next = pre.next;
                pre.next = tarNode;
            }
            tarNode = lastNode.next;
        }
        return helpNode.next;
    }

    /**
     * 归并排序
     * @author ymy
     * @date 2021/11/19 13:28
     * @param head
     * @return com.leetcode.linkedlist.Code03.ListNode
     */
    public ListNode sortList3(ListNode head) {
        int count = 0;
        ListNode kp = head;
        while(kp != null){
            kp = kp.next;
            count ++;
        }
        if(count == 1){
            return head;
        }
        if(count == 2){
            ListNode tar = head;
            if(head.val > head.next.val){
                tar = head.next;
                head.next.next = head;
                head.next = null;
            }
            return tar;
        }
        kp = head;
        int t = count/2;
        while(kp != null){
            kp = kp.next;
            count ++;
            if(count == t){

            }
        }


        System.out.println(count);
        return head;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode tar = head;
        ListNode p1 = l1;
        ListNode p2 = l2;
        while(p1 != null && p2 != null){
            if(p1.val <= p2.val){
                tar.next = p1;
                tar = tar.next;
                p1 = p1.next;
            }else {
                tar.next = p2;
                tar = tar.next;
                p2 = p2.next;
            }
        }
        tar.next = p1 == null ? p2 : p1;
        return head.next;
    }

    static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
